package com.shuo.dsa.niuke;

import com.shuo.dsa.model.ListNode;

import java.util.Stack;

/**
 * 输入两个链表，找出它们的第一个公共结点
 * 思路1: 两个栈, 遍历双list, 然后遍历双栈, 直至取到的节点不同为止
 * 思路2: 用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点
 */
public class FindFirstCommonNode {
    /**
     * 双栈法
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) return null;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        ListNode node = pHead1;
        while (node != null) {
            stack1.push(node);
            node = node.next;
        }
        node = pHead2;
        while (node != null) {
            stack2.push(node);
            node = node.next;
        }
        int len = Math.min(stack1.size(), stack2.size());
        for (int i = 0; i < len; i++) {
            ListNode pre = stack1.peek();
            if (stack1.pop() != stack2.pop())
                return node;
            node = pre;
        }
        return node;
    }
}
